/*
Given two sorted single linked lists list1,list2 write a algorithm to merge the two lists again in sorted order. No new nodes should be created.
- Also give all the test cases for testing this algorithm

*/
#ifndef IOSTREAM
#define IOSTREAM
#endif
#include "functions.h"
using namespace std;

SortedList& merge(SortedList& l_list, SortedList& r_list)// we will not change second list and use list1 as merge base
{
	
	//if they are 2 empty list return l_list;
	if(l_list.head==NULL&&r_list.head==NULL)
		return l_list;

	//if there are any 1 empty one in the sort process in the process stop the merging

	Node* ltraver=l_list.head;//2 traveler initialized
	Node* rtraver=r_list.head;
	Node* pre=NULL;//left list pre
	
	while(ltraver!=NULL&&rtraver!=NULL)
	{
		//if right is bigger then move the right down until right is smaller put the right head before this smaller,compare from rtraveler and ltraverler++
	

		cout<<"left node is "<<ltraver->item.key<<"   right node is "<<rtraver->item.key<<endl;
		if(ltraver->item.lessthen(rtraver->item))
		{
			cout<<"insert "<<rtraver->item.key<<"  after "<<pre->item.key<<endl;
			if(pre==NULL)
			{
				Node*temp=rtraver->next;
			rtraver->next=ltraver;
			rtraver=temp;//move right down 1;
			l_list.head=rtraver;
			l_list.printal();
			
			}
			else
			{
				cout<<"insert "<<rtraver->item.key<<"  after "<<pre->item.key<<endl;
			pre->next=rtraver;
			Node*temp=rtraver->next;
			rtraver->next=ltraver;
			pre=rtraver;
			rtraver=temp;//move right down 1;
			}

			
		}



		//if left is bigger 
		else 
		{
			pre=ltraver;
			ltraver=ltraver->next;
		
		}
	
	
	}

	if(rtraver!=NULL)
		pre->next=rtraver;
	return l_list;

}